package pro.softzhang.algo.lc700;

import pro.softzhang.algo.common.TreeNode;
import pro.softzhang.algo.flag.difficulty.DGreen;
import pro.softzhang.algo.flag.knowledge.KBinarySearchTree;
import pro.softzhang.algo.flag.x.XOptimal;

/**
 *
 */
@DGreen
@KBinarySearchTree
public class LC700_SearchInABinarySearchTree {
    public static void main(String[] args) {

    }

    /**
     * 递归实现
     */
    static
    class Solution {
        public TreeNode searchBST(TreeNode root, int val) {
            if (root == null || root.val == val) return root;
            if (root.val > val) {
                return searchBST(root.left, val);
            } else {
                return searchBST(root.right, val);
            }
        }
    }

    @XOptimal
    static
    class Solution1 {
        public TreeNode searchBST(TreeNode root, int val) {
            while (root != null && root.val != val) {
                root = root.val > val ? root.left : root.right;
            }
            return root;
        }
    }
}
